/*
@Copyright:LintCode
@Author:   tjyemail
@Problem:  http://www.lintcode.com/problem/unique-paths-ii
@Language: C++
@Datetime: 16-02-09 05:23
*/

class Solution {
public:
    /**
     * @param obstacleGrid: A list of lists of integers
     * @return: An integer
     */ 
    int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
        // write your code here
        int F[101][101]={0};
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        for(int i=1;i<=m;++i){
            F[i][1]=1;
			if (obstacleGrid[i-1][0]){
				for(int j=i;j<=m;++j)
					F[j][1]=0;
				break;
			}
		}
        for(int i=1;i<=n;++i){
            F[1][i]=1;
			if (obstacleGrid[0][i-1]){
				for(int j=i;j<=n;++j)
					F[1][j]=0;
				break;
			}
		}
        for(int i=2;i<=m;++i)
            for(int j=2;j<=n;++j)
                F[i][j]=(obstacleGrid[i-1][j-1]?0:F[i][j-1]+F[i-1][j]);
        return F[m][n];
    }
};